It is a significant requirement for a quadrotor trajectory planner to simultaneously guarantee trajectory quality and system lightweight. Many researchers focus on this problem, but there's still a gap between their performance and our common wish. In this paper, we propose an ultra lightweight quadrotor planner with time-optimal primitives. Firstly, a novel motion primitive library is proposed to generate time-optimal and dynamical feasible trajectories offline. Secondly, we propose a fast collision checking method with a deterministic time consumption, independent of the sampling resolution of the primitives. Finally, we select the minimum cost trajectory to execute among the safe primitives based on user-defined requirements. The propsed transformation relation between the local trajectories ensures the smoothness of the global trajectory. The planner reduces unnecessary online computing power consumption as much as possible, while ensuring a high-quality trajectory. Benchmark comparisons show that our method can generate the shortest flight time and distance of trajectory with the lowest computation overload. Challenging real-world experiments validate the robustness of our method.

In environments where many automated guided vehicles (AGVs) operate, planning efficient, collision-free paths is essential. Related research has mainly focused on environments with static passages, resulting in space inefficiency. We define multi-agent and multi-rack path finding (MARPF) as the problem of planning paths for AGVs to convey target racks to their designated locations in environments without passages. In such environments, an AGV without a rack can pass under racks, whereas an AGV with a rack cannot pass under racks to avoid collisions. MARPF entails conveying the target racks without collisions, while the other obstacle racks are positioned without a specific arrangement. AGVs are essential for relocating other racks to prevent any interference with the target racks. We formulated MARPF as an integer linear programming problem in a network flow. To distinguish situations in which an AGV is or is not loading a rack, the proposed method introduces two virtual layers into the network. We optimized the AGVs' movements to move obstacle racks and convey the target racks. The formulation and applicability of the algorithm were validated through numerical experiments. The results indicated that the proposed algorithm addressed issues in environments with dense racks.

Formation flight has a vast potential for aerial robot swarms in various applications. However, existing methods lack the capability to achieve fully autonomous large-scale formation flight in dense environments. To bridge the gap, we present a complete formation flight system that effectively integrates real-world constraints into aerial formation navigation. This paper proposes a differentiable graph-based metric to quantify the overall similarity error between formations. This metric is invariant to rotation, translation, and scaling, providing more freedom for formation coordination. We design a distributed trajectory optimization framework that considers formation similarity, obstacle avoidance, and dynamic feasibility. The optimization is decoupled to make large-scale formation flights computationally feasible. To improve the elasticity of formation navigation in highly constrained scenes, we present a swarm reorganization method that adaptively adjusts the formation parameters and task assignments by generating local navigation goals. A novel swarm agreement strategy called global-remap-local-replan and a formation-level path planner is proposed in this work to coordinate the global planning and local trajectory optimizations. To validate the proposed method, we design comprehensive benchmarks and simulations with other cutting-edge works in terms of adaptability, predictability, elasticity, resilience, and efficiency. Finally, integrated with palm-sized swarm platforms with onboard computers and sensors, the proposed method demonstrates its efficiency and robustness by achieving the largest scale formation flight in dense outdoor environments.

This paper presents a novel and efficient collision checking approach called Updating and Collision Check Skipping Quad-tree (USQ) for multi-robot motion planning. USQ extends the standard quad-tree data structure through a time-efficient update mechanism, which significantly reduces the total number of collision checks and the collision checking time. In addition, it handles transitions at the quad-tree quadrant boundaries based on worst-case trajectories of agents. These extensions make quad-trees suitable for efficient collision checking in multi-robot motion planning of large robot teams. We evaluate the efficiency of USQ in comparison with Regenerating Quad-tree (RQ) from scratch at each timestep and naive pairwise collision checking across a variety of randomized environments. The results indicate that USQ significantly reduces the number of collision checks and the collision checking time compared to other baselines for different numbers of robots and map sizes. In a 50-robot experiment, USQ accurately detected all collisions, outperforming RQ which has longer run-times and/or misses up to 25% of collisions.

While evolutionary computation is well suited for automatic discovery in engineering, it can also be used to gain insight into how humans and organizations could perform more effectively. Using a real-world problem of innovation search in organizations as the motivating example, this article first formalizes human creative problem solving as competitive multi-agent search (CMAS). CMAS is different from existing single-agent and team search problems in that the agents interact through knowledge of other agents' searches and through the dynamic changes in the search landscape that result from these searches. The main hypothesis is that evolutionary computation can be used to discover effective strategies for CMAS; this hypothesis is verified in a series of experiments on the NK model, i.e.\ partially correlated and tunably rugged fitness landscapes. Different specialized strategies are evolved for each different competitive environment, and also general strategies that perform well across environments. These strategies are more effective and more complex than hand-designed strategies and a strategy based on traditional tree search. Using a novel spherical visualization of such landscapes, insight is gained about how successful strategies work, e.g.\ by tracking positive changes in the landscape. The article thus provides a possible framework for studying various human creative activities as competitive multi-agent search in the future.

Problems that claim several agents to find no-conflicts paths from their start locations to their destinations are named as cooperative pathfinding problems. This problem can be efficiently solved by the Multi-agent RRT*(MA-RRT*) algorithm, which offers better scalability than some traditional algorithms, such as Optimal Anytime(OA), in sparse environments. However, MA-RRT* cannot effectively find solutions in relatively dense environments, cause some random samples in the free space cannot be explored by the rapidly random tree, which hinders the application of MA-RRT* in a more complicated real-world. This paper proposes an improved version of MA-RRT *, called Multi-agent RRT* Potential Field (MA-RRT*PF), an anytime algorithm that can efficiently guide the rapidly random tree to the free space in relatively dense environments. It works by incorporating a potential field to the GREEDY function to enhance the ability to avoid the obstacles. The results show that MA-RRT*PF performs much better than MA-RRT* in relatively dense environments in terms of scalability while still maintaining the solution quality.